/**
 * @author hewei
 * @version 1.0
 * @description: 1031. 两个非重叠子数组的最大和
 * @date 2022/10/18 21:02
 */

public class MaxSumTwoNoOverlap {

    public int maxSumTwoNoOverlap(int[] nums, int l, int m) {
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }
        int ans = nums[m + l - 1], lMax = nums[l - 1], mMax = nums[m - 1];
        // 枚举最后一个区间的尾部，那么最后一个区间就已经确定，不是i-l～i，就是i-m～i；
        // 那么另一个就是前面另一个区间的最大值，在遍历的过程中不断更新；
        // 因为不知道最后面的那个区间是l还是m，所以两个区间的最大值都要更新，同时比较时也要两种情况都要比较
        for (int i = m + l; i < nums.length; i++) {
            lMax = Math.max(lMax, nums[i - m] - nums[i - m - l]);
            mMax = Math.max(mMax, nums[i - l] - nums[i - m - l]);
            ans = Math.max(ans, Math.max(lMax + nums[i] - nums[i - m], mMax + nums[i] - nums[i - l]));
        }
        return ans;
    }
}
